Hashing: Strategie di Ridimensionamento

La Necessità del Ri-hash

Per garantire le prestazioni desiderate $O(1)$ nel caso medio per ricerca e inserimento, il Fattore di Carico ( $\lambda = N/M$ ) deve essere rigorosamente limitato, dove $N$ è il numero di elementi e $M$ è la capacità della tabella.

Se $\lambda$ è consentito crescere indefinitamente, le collisioni aumentano esponenzialmente e la complessità temporale media si degrada verso $O(N)$ .

Condizione	Azione Attivata	Impatto
$\lambda < \lambda_{max}$	Standard $O(1)$ inserimento	Efficienza ottimale mantenuta.
$\lambda \geq \lambda_{max}$	Ridimensionamento (Ri-hash)	Ripristina $O(1)$ le prestazioni, ma comporta un costo temporaneo di $O(N)$ costo.

Soglie Comuni ( $\lambda_{max}$ ): 0.70 a 0.75.

Il Processo di Ridimensionamento

Il ridimensionamento richiede il ricalcolo dell'indice hash per ogni singolo elemento attualmente presente nella tabella, un processo noto come Ri-hash.

Determinazione Nuova Capacità: Seleziona una nuova capacità $M_{new}$ , di solito il doppio della capacità corrente ( $M_{new} = 2M$ ). Questo garantisce che il nuovo $\lambda$ sia la metà del valore critico.
Creazione Tabella: Allocare un nuovo array di tabella hash di dimensione $M_{new}$ .
Iterazione Elementi: Scorri tutti i $N$ elementi esistenti nella vecchia tabella.
Ri-hash: Per ogni chiave $k$ , calcola l'indice nuovo usando il modulo aggiornato: $\text{indice}' = h(k) \pmod{M_{new}}$
Inserimento: Inserisci l'elemento nella nuova tabella all'indice $\text{indice}'$ .

Nota: Poiché il modulo cambia, copiare semplicemente l'array è impossibile; ogni elemento deve essere reinserito.

Costo Ammortizzato

Perché il Ridimensionamento è $O(N)$

Il ridimensionamento richiede il trattamento di tutti i $N$ elementi, il che significa che l'operazione stessa impiega $O(N)$ tempo, il che viola temporaneamente l'obiettivo di $O(1)$ inserimento.

Analisi Ammortizzata

Utilizziamo Analisi Ammortizzata per giustificare questo costo. Se la tabella raddoppia la sua dimensione ogni volta che si ridimensiona (crescita esponenziale), il costo elevato di $O(N)$ viene distribuito su un gran numero di inserimenti intermedi $O(1)$ inserimenti.

Il costo medio di qualsiasisingolo inserimento, considerando il ridimensionamento periodico $O(N)$ rimane $O(1)$ .

📝 Quiz Interattivo

1. Una mappa hash ha una capacità $M=50$ e un fattore di carico massimo $\lambda_{max} = 0.6$ . A quale numero di elementi ( $N$ ) deve essere attivato il ridimensionamento?

A) $N = 25$
B) $N = 30$
C) $N = 31$
D) $N = 50$

2. Durante un ridimensionamento, perché non possiamo semplicemente copiare gli elementi dalla vecchia tabella a quella più grande?

A) È computazionalmente più lento rispetto al ri-hash.
B) L'indice hash dipende dalla capacità della tabella ( $M$ ), che è cambiata.
C) Causerebbe frammentazione della memoria.
D) I vecchi dati sono in uno stato di sola lettura.

3. Qual è la complessità temporale ammortizzata di un inserimento in una tabella hash che raddoppia la sua dimensione durante il ridimensionamento?

A) $O(N)$
B) $O(1)$
C) $O(\log N)$
D) $O(N \log N)$

4. Qual è la conseguenza principale del non ridimensionare una tabella hash quando il suo fattore di carico diventa troppo alto?

A) Le prestazioni si degradano verso $O(N)$ a causa di un aumento delle collisioni.
B) La tabella si esaurirà immediatamente.
C) La funzione hash stessa diventa invalida.
D) La tabella elimina automaticamente gli elementi più vecchi.